public class LeetCode167 {
    public int[] twoSum(int[] numbers, int target) {
        int p1 = 0;
        int p2 = numbers.length - 1;
        while (p1 < p2) {
            int sum = numbers[p1] + numbers[p2];
            if (sum == target) {
                //题目要求从一开始
                return new int[]{p1 + 1, p2 + 1};
            } else if (sum < target) {
                p1++;
            } else {
                p2--;
            }
        }
        return new int[]{-1, -1};
    }

    //    二分查找
    public int[] twoSum2(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int diff = target - numbers[i];
            int left = i + 1;
            int right = numbers.length - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (numbers[mid] == diff) {
                    return new int[]{i+1, mid + 1};
                }else if (numbers[mid] < diff){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return new int[]{-1, -1};
    }
}
